package interview;

import java.util.Arrays;

public class Leetcode_面试题_51 {
    public static int reversePairs(int[] nums) {
        return mergeSort(nums, 0, nums.length - 1);
    }

    private static int mergeSort(int[] nums, int left, int right) {
        if (right <= left) {
            return 0;
        }
        int mid = (right + left) >> 1;
        return mergeSort(nums, left, mid) + mergeSort(nums, mid + 1, right) + merge(nums, left, mid, right);
    }

    private static int merge(int[] nums, int left, int mid, int right) {
        int i = left;
        int j = mid + 1;
        int k = 0;
        int count = 0;
        int res[] = new int[right - left + 1];
        while (i <= mid && j <= right) {
            //如果j位置小于i位置，那么j位置小于i位置后所有的左半边的数
            if (nums[i] > nums[j]) {
                count += mid - i + 1;
            }
            res[k++] = nums[i] <= nums[j] ? nums[i++] : nums[j++];
        }
        while (i <= mid) {
            res[k++] = nums[i++];
        }
        while (j <= right) {
            res[k++] = nums[j++];
        }
        for (int m = 0; m < res.length; m++) {
            nums[left + m] = res[m];
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(reversePairs(new int[]{7, 5, 6, 4}));
    }
}
